package com.apkcore.bl;

public class _887鸡蛋掉落 {
    public static void main(String[] args) {
        System.out.println(new _887鸡蛋掉落().superEggDrop(3, 14));
    }

    int superEggDrop(int K, int N) {
        int[][] dp = new int[N + 1][K + 1];
        // 初始化dp数组
        for (int i = 0; i <= N; i++) dp[i][1] = i;

        for (int i = 1; i <= N; i++) {
            for (int k = 2; k <= K; k++) {
                int res = Integer.MAX_VALUE;
                for (int j = 1; j <= i; j++) {
                    res = Math.min(res , Math.max(dp[j-1][k-1], dp[i-j][k]) + 1);
                }
                dp[i][k] = res;
            }
        }
        return dp[N][K];
    }

    public int superEggDrop2(int k, int n) {
        if (n < 2 || k == 1)
            return n;
        int[][] dp = new int[k + 1][n + 1];
        int m = 0;
        //最坏情况下最多能测试 n 层楼
        while (dp[k][m] < n) {
            m++;
            for (int i = 1; i <= k; i++) {
                dp[i][m] = dp[i - 1][m - 1] + dp[i][m - 1] + 1;
            }
        }
        return m;
    }
}
